/// @tags: BinomInversion
#include <cstdio>
#include <cstring>
#include <iostream>
#define rint register int

using std::cin;
using std::cout;

namespace BlueQuantum {

typedef long long LL;

constexpr int mod = 1e6 + 3, maxs = 55, maxn = 16;

char s[maxn][maxs], pin[maxs];
int pcnt, n, m, k;
int qpow[maxs], f[maxn], c[maxs][maxs], p[maxs];

void dfs(int x, int cnt) {
  if (n - x + 1 + cnt < k) return;
  if (x == n + 1) {
    f[cnt] += qpow[m - pcnt];
    if (f[cnt] >= mod) f[cnt] -= mod;
    return;
  }
  dfs(x + 1, cnt);
  for (int i = 0; i < m; ++i)
    if (pin[i] && s[x][i] >= 'a' && pin[i] != s[x][i]) return;
  int ori = pcnt;
  for (int i = 0; i < m; ++i)
    if (!pin[i] && s[x][i] != '?') pin[i] = s[x][i], p[++pcnt] = i;
  dfs(x + 1, cnt + 1);
  while (pcnt > ori) pin[p[pcnt--]] = 0;
}

void solve() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> s[i];
  m = strlen(s[1]);
  memset(f, 0, sizeof(f));
  dfs(1, 0);
  int ans = 0;
  for (int i = k; i <= n; ++i) {
    (i - k)& 1 ? ans += mod - (LL)c[i][k] * f[i] % mod : ans += (LL)c[i][k] * f[i] % mod;
    if (ans >= mod) ans -= mod;
  }
  cout << ans << '\n';
}

inline int main() {
  for (int i = 0; i < maxn; ++i) {
    c[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
      if (c[i][j] > mod) c[i][j] -= mod;
    }
  }
  qpow[0] = 1;
  for (int i = 1; i < maxs; ++i) qpow[i] = qpow[i - 1] * 26 % mod;
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P2167 [SDOI2009] Bill的挑战.in", "r", stdin);
  freopen("P2167 [SDOI2009] Bill的挑战.out", "w", stdout);
#endif
#endif

  std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
